package middle;

public class Solution_300 {

    public int lengthOfLIS(int[] nums) {
        int max = 1;
        int[] counts = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            int count = 0;
            for (int j = i - 1; j >= 0; j--) {
                if (nums[j] < nums[i]) {
                    count = Math.max(counts[j], count);
                }
            }
            count++;
            max = Math.max(max, count);
            counts[i] = count;
        }
        for (int i = 0; i < counts.length; i++) {
            System.out.println("i = " + i + ";  num = " + nums[i] + ";  count = " + counts[i]);
        }
        return max;
    }

    public static void main(String[] args) {
        Solution_300 model = new Solution_300();
        System.out.println(model.lengthOfLIS(new int[]{10, 9, 2, 5, 3, 7, 101, 18}));
        System.out.println(model.lengthOfLIS(new int[]{0, 1, 0, 3, 2, 3}));
        System.out.println(model.lengthOfLIS(new int[]{7, 7, 7, 7, 7, 7, 7}));
    }
}
